class Solution {
public:
    int nthUglyNumber(int n) {
        if(n < 2 || n > 1690)  return 1; 
        /*
        正确理解：丑数只能被2,3,5整除，也就是说，number连续除2,3,5，如果最后结果是1，则说明number为丑数
        直接法：依次判断每个数是否为丑数，时间复杂度过高
        */
        int number = 1;
        while(n > 1)
        {
            ++number;
            if(isUglyNumber(number))  --n;
        }
        
        return number;
    }

    bool isUglyNumber(int number){
        while(number % 2 == 0)  number /= 2;
        while(number % 3 == 0)  number /= 3;
        while(number % 5 == 0)  number /= 5;

        return (number == 1) ? true : false;
    }
};